package weka.classifiers.trees;

import java.util.Enumeration;

import weka.core.Instance;
import weka.core.Instances;
import weka.core.Attribute;
import weka.core.Utils;

public class LSID3Utils
{
	 public static final int FULL_GAIN = -1;						//Indication that attribute has full gain.
	
	 /**
	   * Computes information gain for an attribute.
	   *
	   * @param data the data for which info gain is to be computed
	   * @param att the attribute
	   * @return the information gain for the given attribute and data
	   * @throws Exception if computation fails
	   */
	  public static double computeInfoGain(Instances data, Attribute att) 	     
	  {
	    double infoGain = computeEntropy(data);
	    double restEntropy = 0.0;
	    Instances[] splitData = splitData(data, att);
	    
	    for (int j = 0; j < att.numValues(); j++) 
	    {
	      if (splitData[j].numInstances() > 0) 
	      {
	    	restEntropy +=	((double) splitData[j].numInstances() /
	                		(double) data.numInstances()) *
	                		computeEntropy(splitData[j]);
	      }
	    }
	    
	    if (restEntropy == 0)
	    {
	    	infoGain = FULL_GAIN;
	    }
	    else
	    {
    	   infoGain -= restEntropy;
	    }
	    
	    return infoGain;
	  }

	/**
	   * Splits a dataset according to the values of a nominal attribute.
	   *
	   * @param data the data which is to be split
	   * @param att the attribute to be used for splitting
	   * @return the sets of instances produced by the split
	   */
	  public static Instances[] splitData(Instances data, Attribute att) 
	  {
	    Instances[] splitData = new Instances[att.numValues()];
	    
	    for (int j = 0; j < att.numValues(); j++) 
	    {
	      splitData[j] = new Instances(data, data.numInstances());
	    }
	    
	    Enumeration instEnum = data.enumerateInstances();
	    
	    while (instEnum.hasMoreElements()) 
	    {
	      Instance inst = (Instance) instEnum.nextElement();
	      splitData[(int) inst.value(att)].add(inst);
	    }
	    
	    for (int i = 0; i < splitData.length; i++) 
	    {
	      splitData[i].compactify();
	    }
	    
	    return splitData;
	  }
	  
	  /**
	   * Computes the entropy of a dataset.
	   * 
	   * @param data the data for which entropy is to be computed
	   * @return the entropy of the data's class distribution
	   * @throws Exception if computation fails
	   */
	  private static double computeEntropy(Instances data) 
	  {
	    double [] classCounts = new double[data.numClasses()];
	    Enumeration instEnum = data.enumerateInstances();
	    while (instEnum.hasMoreElements()) 
	    {
	      Instance inst = (Instance) instEnum.nextElement();
	      classCounts[(int) inst.classValue()]++;
	    }
	    
	    double entropy = 0.0;
	    for (int j = 0; j < data.numClasses(); j++) 
	    {
	      if (classCounts[j] > 0) 
	      {
	        entropy += (classCounts[j] / data.numInstances()) * Utils.log2(classCounts[j] / data.numInstances());
	      }
	    }
	    
	    //entropy /= (double) data.numInstances();
	    return -entropy;
	    //return entropy + Utils.log2(data.numInstances());
	    //return entropy + Utils.log2(data.numInstances());
	  }
}